#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
"""
@UserFor     :   ***  动态规划解析完全平方数  ***
@File        :   middle-279-完全平方数.py    
@Email       :   18574945291@163.com
@Modify Time :   2021-02-15 17:59
@Author      :   code_wizard (wll) 
"""

"""
    对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割
条件的位置。我们定义一个一维矩阵 dp，其中 dp[i] 表示数字 i 最少可以由几个完全平方数相加
构成。在本题中，位置 i 只依赖 i - k*k 的位置，如 i - 1、i - 4、i - 9 等等，才能满足完全平方分割
的条件。因此 dp[i] 可以取的最小值即为 1 + min(dp[i-1], dp[i-4], dp[i-9] ···)。
"""
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0 for i in range(n)]
        for i in range(1,n):
            print(dp)
            j = 1
            while j*j < i:
                dp[i] = min(dp[i],dp[i-j*j]+1)
                j += 1
        return dp[-1]

if __name__ == '__main__':
    obj = Solution()
    print(obj.numSquares(13))